package com.simon.study.algorithm.leetcode;

/**
 * <p>
 *
 * @author simon
 */
public class MinSumSquareDiff02333Dup {
    public static void main(String[] args) {
        int[] nums1 = new int[]{3,5,4,4};
        int[] nums2 = new int[]{1,2,1,0};
        int k1 = 2, k2 = 4;

        minSumSquareDiff(nums1,nums2, k1, k2);
    }

    public static long minSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2) {
        long ans = 0;
        int[] arr = new int[100010];
        for(int i=0;i<nums1.length;i++) {
            arr[Math.abs(nums1[i]-nums2[i])]++;
        }
        int k = k1+k2;
        int i=100000;
        for(;i>=1;i--) {
            if(arr[i] == 0) continue;
            if(k>arr[i]) {
                arr[i-1] += arr[i];
                k -= arr[i];
            }else if(k == arr[i]) {
                arr[i-1] += arr[i];
                i--;
                k = 0;
                break;
            }else {
                arr[i-1] += k;
                arr[i] -= k;
                break;
            }
        }
        for(;i>=1;i--) {
            if(arr[i] == 0) continue;
            ans += (long)i*i*arr[i];
        }
        return ans;
    }
}
